#include <stdio.h>
#include <string.h>
#include <stdlib.h>

char *longestCommonSubstring(char *s1, char *s2)
{
    int len1 = strlen(s1);
    int len2 = strlen(s2);
    int max_len = 0; // 最大公串长度
    int end1 = 0;    // 最大公串在s1中的结束位置

    // 创建二维数组dp，dp[i][j]表示s1[0...i-1]和s2[0...j-1]的最长公共后缀长度
    int **dp = (int **)malloc((len1 + 1) * sizeof(int *));
    for (int i = 0; i <= len1; i++)
    {
        dp[i] = (int *)malloc((len2 + 1) * sizeof(int));
        memset(dp[i], 0, (len2 + 1) * sizeof(int));
    }
    /*dp是一个二维数组，用于存储子问题的解。
      dp[i][j]表示s1[0...i-1]和s2[0...j-1]的最长公共后缀长度。
      使用malloc动态分配内存，
      创建一个(len1 + 1) x (len2 + 1)的二维数组，
      并使用memset将所有元素初始化为0。*/

    // 填充dp数组
    for (int i = 1; i <= len1; i++)
    {
        for (int j = 1; j <= len2; j++)
        {
            if (s1[i - 1] == s2[j - 1])
            {
                dp[i][j] = dp[i - 1][j - 1] + 1;
                if (dp[i][j] > max_len)
                {
                    max_len = dp[i][j];
                    end1 = i - 1;
                }
            }
        }
    }

    // 根据最大公串的长度和结束位置，从s1中截取最大公串
    char *result = (char *)malloc((max_len + 1) * sizeof(char));
    strncpy(result, s1 + end1 - max_len + 1, max_len);
    result[max_len] = '\0';

    // 释放dp数组内存
    for (int i = 0; i <= len1; i++)
    {
        free(dp[i]);
    }
    free(dp);

    return result;
}

int main()
{
    char s1[] = "abcdefg";
    char s2[] = "xycdefz";
    char *result = longestCommonSubstring(s1, s2);
    printf("最长公共子串为：%s\n", result);
    free(result); // 释放result内存
    return 0;
}